#include <iostream>
using namespace std;

// 多项式项节点
typedef struct PNode {
    double coef;    // 系数
    int exp;        // 指数
    struct PNode *next;
} PNode, *Polynomial;

// 初始化多项式
void InitPoly(Polynomial &P) {
    P = new PNode;
    P->next = NULL;
}

// 销毁多项式
void DestroyPoly(Polynomial &P) {
    PNode *p = P->next;
    while (p != NULL) {
        PNode *temp = p;
        p = p->next;
        delete temp;
    }
    delete P;
    P = NULL;
}

// 添加项到多项式（按指数降序排列）
void AddTerm(Polynomial &P, double coef, int exp) {
    if (coef == 0) return;  // 系数为0不添加
    
    PNode *p = P;
    
    // 找到插入位置（保持指数降序）
    while (p->next != NULL && p->next->exp > exp) {
        p = p->next;
    }
    
    // 如果指数相同，合并系数
    if (p->next != NULL && p->next->exp == exp) {
        p->next->coef += coef;
        if (p->next->coef == 0) {  // 合并后系数为0，删除该节点
            PNode *temp = p->next;
            p->next = temp->next;
            delete temp;
        }
    } else {  // 创建新节点
        PNode *newNode = new PNode;
        newNode->coef = coef;
        newNode->exp = exp;
        newNode->next = p->next;
        p->next = newNode;
    }
}

// 创建多项式（从用户输入）
void CreatePoly(Polynomial &P) {
    cout << "创建多项式（输入0 0结束）:" << endl;
    double coef;
    int exp;
    
    while (true) {
        cout << "输入系数和指数: ";
        cin >> coef >> exp;
        if (coef == 0 && exp == 0) break;
        AddTerm(P, coef, exp);
    }
}

// 创建多项式（从数组）
void CreatePolyFromArray(Polynomial &P, double coefs[], int exps[], int n) {
    for (int i = 0; i < n; i++) {
        AddTerm(P, coefs[i], exps[i]);
    }
}

// 显示多项式
void DisplayPoly(Polynomial P) {
    if (P->next == NULL) {
        cout << "0" << endl;
        return;
    }
    
    PNode *p = P->next;
    bool firstTerm = true;
    
    while (p != NULL) {
        // 处理符号显示
        if (p->coef > 0 && !firstTerm) {
            cout << " + ";
        } else if (p->coef < 0) {
            cout << " - ";
        }
        
        // 显示系数（绝对值）
        double absCoef = (p->coef < 0) ? -p->coef : p->coef;
        
        // 显示项
        if (p->exp == 0) {
            cout << absCoef;
        } else if (p->exp == 1) {
            if (absCoef == 1) {
                cout << "x";
            } else {
                cout << absCoef << "x";
            }
        } else {
            if (absCoef == 1) {
                cout << "x^" << p->exp;
            } else {
                cout << absCoef << "x^" << p->exp;
            }
        }
        
        p = p->next;
        firstTerm = false;
    }
    cout << endl;
}

// 多项式相加：Pa = Pa + Pb
void AddPoly(Polynomial &Pa, Polynomial Pb) {
    PNode *p1 = Pa->next;  // Pa的工作指针
    PNode *p2 = Pb->next;  // Pb的工作指针
    PNode *p3 = Pa;        // Pa的结果指针（指向当前节点的前驱）
    
    while (p1 != NULL && p2 != NULL) {
        if (p1->exp > p2->exp) {
            // Pa的当前项指数大，保留该项
            p3->next = p1;
            p3 = p1;
            p1 = p1->next;
        } else if (p1->exp < p2->exp) {
            // Pb的当前项指数大，将该项插入到Pa中
            PNode *temp = new PNode;
            temp->coef = p2->coef;
            temp->exp = p2->exp;
            temp->next = p1;
            p3->next = temp;
            p3 = temp;
            p2 = p2->next;
        } else {
            // 指数相等，系数相加
            double sum = p1->coef + p2->coef;
            if (sum != 0) {
                // 系数和不为0，更新系数
                p1->coef = sum;
                p3->next = p1;
                p3 = p1;
                p1 = p1->next;
                p2 = p2->next;
            } else {
                // 系数和为0，删除Pa的当前项
                PNode *temp = p1;
                p1 = p1->next;
                delete temp;
                p2 = p2->next;
            }
        }
    }
    
    // 处理剩余项
    if (p2 != NULL) {
        p3->next = p2;
    } else {
        p3->next = p1;
    }
}

// 多项式相加：返回新多项式 Pc = Pa + Pb
Polynomial AddPolyNew(Polynomial Pa, Polynomial Pb) {
    Polynomial Pc;
    InitPoly(Pc);
    
    PNode *p1 = Pa->next;
    PNode *p2 = Pb->next;
    PNode *p3 = Pc;
    
    while (p1 != NULL && p2 != NULL) {
        PNode *newNode = new PNode;
        
        if (p1->exp > p2->exp) {
            newNode->coef = p1->coef;
            newNode->exp = p1->exp;
            p1 = p1->next;
        } else if (p1->exp < p2->exp) {
            newNode->coef = p2->coef;
            newNode->exp = p2->exp;
            p2 = p2->next;
        } else {
            double sum = p1->coef + p2->coef;
            if (sum == 0) {
                delete newNode;
                p1 = p1->next;
                p2 = p2->next;
                continue;
            }
            newNode->coef = sum;
            newNode->exp = p1->exp;
            p1 = p1->next;
            p2 = p2->next;
        }
        
        newNode->next = NULL;
        p3->next = newNode;
        p3 = newNode;
    }
    
    // 处理剩余项
    while (p1 != NULL) {
        PNode *newNode = new PNode;
        newNode->coef = p1->coef;
        newNode->exp = p1->exp;
        newNode->next = NULL;
        p3->next = newNode;
        p3 = newNode;
        p1 = p1->next;
    }
    
    while (p2 != NULL) {
        PNode *newNode = new PNode;
        newNode->coef = p2->coef;
        newNode->exp = p2->exp;
        newNode->next = NULL;
        p3->next = newNode;
        p3 = newNode;
        p2 = p2->next;
    }
    
    return Pc;
}

// 复制多项式
Polynomial CopyPoly(Polynomial P) {
    Polynomial newPoly;
    InitPoly(newPoly);
    
    PNode *p = P->next;
    PNode *q = newPoly;
    
    while (p != NULL) {
        PNode *newNode = new PNode;
        newNode->coef = p->coef;
        newNode->exp = p->exp;
        newNode->next = NULL;
        
        q->next = newNode;
        q = newNode;
        p = p->next;
    }
    
    return newPoly;
}

int main() {
    Polynomial Pa, Pb, Pc;
    
    // 初始化多项式
    InitPoly(Pa);
    InitPoly(Pb);
    
    cout << "=== 稀疏多项式相加演示 ===" << endl;
    
    // 创建第一个多项式
    cout << "\n创建第一个多项式:" << endl;
    CreatePoly(Pa);
    cout << "多项式A: ";
    DisplayPoly(Pa);
    
    // 创建第二个多项式
    cout << "\n创建第二个多项式:" << endl;
    CreatePoly(Pb);
    cout << "多项式B: ";
    DisplayPoly(Pb);
    
    // 方法1：Pa = Pa + Pb（会改变Pa）
    Polynomial Pa_copy = CopyPoly(Pa);  // 备份Pa
    AddPoly(Pa, Pb);
    cout << "\n方法1 - A = A + B:" << endl;
    cout << "结果多项式: ";
    DisplayPoly(Pa);
    
    // 方法2：Pc = Pa + Pb（不改变原多项式）
    Pc = AddPolyNew(Pa_copy, Pb);
    cout << "\n方法2 - C = A + B:" << endl;
    cout << "结果多项式: ";
    DisplayPoly(Pc);
    
    // 示例：使用数组创建多项式
    cout << "\n=== 数组创建多项式示例 ===" << endl;
    Polynomial Pd, Pe;
    InitPoly(Pd);
    InitPoly(Pe);
    
    double coefs1[] = {3, 2, 1};
    int exps1[] = {3, 1, 0};
    CreatePolyFromArray(Pd, coefs1, 3, 3);
    cout << "多项式D: ";
    DisplayPoly(Pd);
    
    double coefs2[] = {4, -2, 5};
    int exps2[] = {4, 1, 0};
    CreatePolyFromArray(Pe, coefs2, 3, 3);
    cout << "多项式E: ";
    DisplayPoly(Pe);
    
    Polynomial Pf = AddPolyNew(Pd, Pe);
    cout << "D + E = ";
    DisplayPoly(Pf);
    
    // 释放内存
    DestroyPoly(Pa);
    DestroyPoly(Pb);
    DestroyPoly(Pc);
    DestroyPoly(Pa_copy);
    DestroyPoly(Pd);
    DestroyPoly(Pe);
    DestroyPoly(Pf);
    
    return 0;
}